
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}
struct Solution;

impl Solution {
    /// 算出所有的值，存到Hasmap里面，取最频繁的哪个
    pub fn find_frequent_tree_sum(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        if root.is_none() {
            return vec![];
        }

        let mut map = HashMap::new();

        let mut res = Vec::new();

        Solution::insert_map(&root, &mut map);
        let max = *map.values().max().unwrap();

        map.into_iter().for_each(|(key, val)| {
            if val == max {
                res.push(key);
            }
        });

        res
    }

    /// 计算出所有的可能性，初入map
    fn insert_map(root: &Option<Rc<RefCell<TreeNode>>>, map: &mut HashMap<i32, i32>) -> i32 {
        if let Some(root_rc) = root {
            let left = Solution::insert_map(&root_rc.borrow().left, map);
            let right = Solution::insert_map(&root_rc.borrow().right, map);

            let root_sum = root_rc.borrow().val + left + right;
            let ori_val = map.get(&root_sum);

            match ori_val {
                None => map.insert(root_sum, 1),

                Some(val) => {
                    let val = *val;
                    map.insert(root_sum, val + 1)
                }
            };

            return root_sum;
        }
        0
    }
}


fn main() {
    Solution::find_frequent_tree_sum(None);
}

